package woa.array;

import java.util.Arrays;

/**
 * 长度最小的子数组
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不
 * 存在符合条件的子数组，返回 0 。
 * <p>
 * 输入：target = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 *
 * @author wangpeng
 * @date 2021/11/14
 */
public class MinSubArrayLenProblem {

    /**
     * 求和运算有冗余计算
     * 超出时间限制
     *
     * @param target
     * @param nums
     *
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int r = 0;
        int len = nums.length;
        for (int s = 0; s < len; s++) {
            for (int i = 0; i < len - s; i++) {
                int sum = sum(nums, i, s);
                if (sum >= target) {
                    return s + 1;
                }
            }
        }
        return r;
    }

    /**
     * 求和
     *
     * @param nums
     * @param i
     * @param step
     *
     * @return
     */
    public static int sum(int[] nums, int i, int step) {
        int sum = 0;
        for (int s = i; s <= i + step; s++) {
            sum += nums[s];
        }
        return sum;
    }

    /**
     * 优化1：减少了加法计算的冗余
     *
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen1(int target, int[] nums) {
        int r = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int t = target;
            for (int j = i; j < nums.length; j++) {
                t = t - nums[j];
                if (t <= 0 && j - i + 1 < r) {
                    r = j - i + 1;
                }
            }

        }
        return r == Integer.MAX_VALUE ? 0 : r;
    }

    /**
     * 滑动窗口
     *
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen2(int target, int[] nums) {
        int r = Integer.MAX_VALUE;
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int i = 0, j = 0, sum = nums[0];
        while (i <= j && j < len) {
            if (sum >= target) {
                if (j - i + 1 < r) {
                    r = j - i + 1;
                }
                sum = sum - nums[i];
                i++;
            } else {
                j++;
                if (j < len) {
                    sum = sum + nums[j];
                }
            }
        }
        return r == Integer.MAX_VALUE ? 0 : r;
    }

    /**
     * 前缀和+二分查找
     * 前缀和构造有序，二分查找获取索引位置
     *
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen3(int target, int[] nums) {
        int r = Integer.MAX_VALUE;
        int len = nums.length;
        int[] sum = new int[len + 1];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        for (int i = 0; i < len; i++) {
            int bound = Arrays.binarySearch(sum, target);
            if (-bound <= len + 1) {

                if (bound < 0) {
                    bound = -bound - 1;
                }
                if (bound - i < r) {
                    r = bound - i;
                }

            }
            target = target + nums[i];
        }
        return r == Integer.MAX_VALUE ? 0 : r;
    }

    public static void main(String[] args) {
        System.out.println(minSubArrayLen3(1, new int[]{1,2,3,4,5}));
    }
}
